//解数独 力扣37
//对棋盘的回溯算法（二维递归）：树层遍历是数字1—9，树枝遍历是棋盘上的每一个方格
//无需找出所有情况，找到一个满足条件的结果就返回：使用bool类型的backtracking
//按某个方形范围检查棋盘的算法（九宫格）
class Solution {
public:
	bool isvalid(vector<vector<char>>& board,int row,int col,int k)
	{
		//检查行
		for(int i = 0; i < 9; i++)
			if(board[row][i] == k+'0') return false;
		//检查列
		for(int i = 0; i < 9; i++)
			if(board[i][col] == k+'0') return false;
		//检查所属九宫格
		int startrow = row/3*3;
		int startcol = col/3*3;
		for(int i = startrow; i < startrow + 3; i++)
		{
			for(int j = startcol; j <startcol + 3; j++)
			{
				if(board[i][j] == k+'0') return false;
			}
		} 
		return true;
	}
	bool backtracking(vector<vector<char>>& board)
	{
		for(int row = 0; row < 9; row++)
		{
			for(int col = 0; col < 9; col++)
			{
				if(board[row][col] == '.')
				{
					for(int k = 1; k <= 9; k++)
					{
						if(isvalid(board,row,col,k))
						{
							board[row][col] = k+'0';
							if(backtracking(board) == true) return true;
							board[row][col] = '.';
						}
					}
					return false;
				}
			}
		}
		return true;
		
	}
	void solveSudoku(vector<vector<char>>& board) {
		backtracking(board);
		return ;
	}
};
